# -*- coding: utf-8 -*-

"""1027. 最长等差数列
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：
输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：
2 <= nums.length <= 1000
0 <= nums[i] <= 500"""

from collections import Counter

class Solution:
    """
    如上示例3：nums = [20,1,15,3,10,5,8]
    毫无疑问的是，需要对每个元素前面的数求差（用图更直观），这样才能在总的差关系图中找到最长的差相等的数列。
    如下矩阵表示 i 与其前面每个元素 j 的差值。
            20      1       15      3       10      5       8   (i)
        20  0       -19     -5      -17     -10     -15     -12
        1           0       14      2       9       4       7
        15                  0       -12     -5      -10     -7
        3                           0       7       2       5
        10                                  0       -10     -2
        5                                           0       3
        8                                                   0
        (j)
    当 i 为 15 时，其与前面的元素差值为 (-5, 14), 其与后面的元素差值为 (-12, -5, -10, -7)。前后有相同的差值 -5 所以三元组 (20, 15, 10) 就是一个等差数列，同理 (1, 3, 5) 也是。
    所以我们可以先拿出所有的等差数列三元组，然后拼接这些三元组从而找到最长等差序列。
    或者把三元组打散成 (20, 15), (15, 10) 这样的，分递增、递减两类序列，分别排序后，不就是求差值相同的最长子序列了吗？
    ----------------------------------------------------------
    三元组换成二元组排序还不行，(2,4,6), (4,6,8), (8,10,12)，甚至即使用三元组也不行，因为不知道这三个元组实际上在序列上的先后关系。
    所以还是应该以地址组成的三元组为等差数列，而不是以值表示，如 (j, i, k, d) 表示编号 j, i, k 上的值是一个以 d 为差值的等差数列。问题的关键是用地址，而无关三元组还是二元组。
    然后可以转化 (j, i, k, d) => (j, i, d), (i, k, d)。一样的分升序或降序两个类型，排序后，计算最大增长子序列即可。
    """
    def longestArithSeqLength(self, nums: list) -> int:
        count = len(nums)
        diff = [[0 for _ in range(count)] for _ in range(count)]
        # i = 0
        # while i < count:
        #     j = 0
        #     while j < i:
        #         diff[j][i] = nums[i] - nums[j]
        #         j += 1
        #     i += 1

        # # 找等差数列这一步非常耗时间，三层循环嵌套，可以这样考虑，邻接的两个等差数列，是不是越收缩越好，前后都有更大可能接上
        # eq_diff_add, eq_diff_sub = set(), set()
        # i = 0
        # while i < count:
        #     j = 0
        #     while j < i:
        #         k = i+1
        #         while k < count:
        #             if (d:=diff[j][i]) == diff[i][k]:
        #                 if d > 0:
        #                     eq_diff_add.add((j, i, d))
        #                     eq_diff_add.add((i, k, d))
        #                 elif d < 0:
        #                     eq_diff_sub.add((j, i, d))
        #                     eq_diff_sub.add((i, k, d))
        #             k += 1
        #         j += 1
        #     i += 1

        i = 0
        while i < count:
            diff[i][i] = (dict(), dict())     # 中间斜线用来缓存入、出差值
            i += 1

        i = 0
        while i < count:
            inDiff = diff[i][i][0]
            j = 0
            while j < i:
                outDiff = diff[j][j][1]
                d = diff[j][i] = nums[i] - nums[j]
                inDiff[d] = max(inDiff.get(d, -1), j)     # 差值相等的时候，j 越靠近 i 越好
                outDiff[d] = min(outDiff.get(d, count), i)
                j += 1
            i += 1

        eq_diff_add, eq_diff_sub = set(), set()
        i = 0
        while i < count:
            inDiff, outDiff = diff[i][i][0], diff[i][i][1]
            for d in (set(inDiff.keys()) & set(outDiff.keys())):
                if d > 0:
                    eq_diff_add.add((inDiff[d], i, d))
                    eq_diff_add.add((i, outDiff[d], d))
                elif d < 0:
                    eq_diff_sub.add((inDiff[d], i, d))
                    eq_diff_sub.add((i, outDiff[d], d))
            i += 1

        eq_diff_add = Solution.quick_sort(eq_diff_add)
        eq_diff_sub = Solution.quick_sort(eq_diff_sub)
        # print(eq_diff_add)
        # print(eq_diff_sub)
        return max(Solution.get_longest(eq_diff_add), Solution.get_longest(eq_diff_sub), max(Counter(nums).values()))

    @staticmethod
    def quick_sort(eq_diff):
        seq = list(eq_diff)
        def lt(x, y):
            if x[0] < y[0]:
                return True
            elif x[0] == y[0] and x[1] < y[1]:
                return True
            else:
                return False

        def gt(x, y):
            if x[0] > y[0]:
                return True
            elif x[0] == y[0] and x[1] > y[1]:
                return True
            else:
                return False

        def do(m, n):
            i, j, pivot = m, n, seq[n]
            while True:
                while i < j and lt(seq[i], pivot):
                    i += 1
                while i < j and gt(seq[j], pivot):
                    j -= 1
                if i >= j:
                    p = i
                    break
                else:
                    seq[i], seq[j] = seq[j], seq[i]
            if m < p-1:
                do(m, p-1)
            if p+1 < n:
                do(p+1, n)

        if seq:
            do(0, len(seq)-1)
        return seq

    @staticmethod
    def get_longest(seq):
        if not seq:
            return 2

        count = len(seq)
        dp = [1 for _ in range(count)]
        i = 0
        while i < count:
            j = 0
            while j < i:
                if seq[j][2] == seq[i][2] and seq[j][1] == seq[i][0]:
                    dp[i] = max(dp[j]+1, dp[j])
                j += 1
            i += 1

        return max(dp)+1


if __name__ == '__main__':
    # rs = Solution().longestArithSeqLength([12,28,13,6,34,36,53,24,29,2,23,0,22,25,53,34,23,50,35,43,53,11,48,56,44,53,31,6,31,57,46,6,17,42,48,28,5,24,0,14,43,12,21,6,30,37,16,56,19,45,51,10,22,38,39,23,8,29,60,18])
    rs = Solution().longestArithSeqLength([214,450,10,56,35,16,45,347,375,208,398,46,284,489,415,380,409,106,30,66,39,411,410,201,105,345,136,76,327,451,71,328,496,248,425,97,76,193,391,429,191,36,407,172,90,163,309,37,403,156,257,77,338,457,445,357,142,493,500,165,440,154,88,193,359,296,70,97,364,84,395,240,2,74,219,277,447,149,3,297,40,196,96,161,147,106,27,429,348,436,42,494,371,331,104,10,283,415,444,126,476,392,25,437,167,148,251,275,94,52,325,459,353,247,266,129,479,363,493,375,110,420,430,97,84,31,118,150,164,188,456,117,158,144,482,150,179,6,164,73,438,295,123,2,402,111,182,161,350,260,486,18,285,485,281,131,486,121,116,253,323,423,47,328,139,169,32,148,256,397,267,484,312,50,123,250,416,390,445,87,281,174,93,15,293,471,103,280,42,147,111,194,188,338,396,340,500,92,240,480,153,162,206,277,208,401,414,60,257,167,419,175,175,100,314,449,469,246,412,424,52,303,83,9,30,4,245,106,91,354,90,347,460,208,217,197,480,412,288,222,182,443,19,454,91,74,136,309,236,412,8,64,422,87,54,330,276,256,12,180,340,144,487,302,418,130,50,446,487,169,204,403,229,63,399,430,272,473,370,456,415,384,418,149,22,15,364,173,213,84,185,236,11,353,433,345,25,413,200,107,369,193,68,300,199,450,490,230,141,112,154,43,490,206,11,55,204,318,373,180,253,357,486,441,180,441,459,47,387,213,120,462,301,21,139,306,497,264,342,446,311,305,448,21,279,471,496,419,462,358,216,490,237,312,159,90,34,36,352,119,372,290,42,114,162,3,369,122,127,236,464,10,204,225,219,221,443,101,15,263,313,498,164,451,387,217,364,316,371,263,380,96,30,65,417,290,451,207,351,317,457,366,350,2,414,375,177,447,409,272,252,486,156,87,200,116,201,498,342,98,67,279,466,271,75,161,492,237,481,356,403,64,473,362,56,466,175,99,197,308,327,413,343,474,446,76,375,68,479,490,167,339,249,419,424,355,101,371,84,86,270,335,244,293,75,121,118,89,171,197,221,15,234,402,239,225,475,426,337,92,432,253,210,163,251,219,440,492,280,317,336,148,302,276,353,446,448,83,444,304,244,169,45,65,202,62,318,457,431,161,471,54,288,150,280,159,376,169,115,458,371,458,446,146,232,153,487])
    print(rs)
